#include <iostream>
#include <fstream>
#include <sstream>
#include <stream>
#include <stdio.h>
#include <stdlib>
#define abc 123
#define bool char
// lalala
#define working 1
// dont want this
//#include <stdlib>

using namespace std;

// comment
// //hahahah123
template <typename T> class Stack {
  public:
    Stack(int size) {
      base = new T[size];
      top = base; // 栈空
      this->size = size;
    }

    void push(T element) {
      if (top == base + size) throw -1; // 栈满
      *(top++) = element;
    }

    T pop() {
      if (top == base) throw -2; // 栈空
      T tmp = *(--top);
      return tmp;
    }

    T getTop() {
      if (top == base) throw -2; // 栈空
      return *top;
    }

    int getStackLength() {
      return top - base;
    }

    char isStackBlank() {
      return !getStackLength();
    }

  private:
    T *base, *top;
    int size;
};

// 双值链表节点
template <class C, typename P> class PairedListNode {
  public:
    PairedListNode<C, P> *next;
    PairedListNode() : c(NULL), p(NULL), next(NULL) {}
    PairedListNode(C c, P p, PairedListNode<C, P>* next) : c(c), p(p), next(next) {}
    PairedListNode(C c, P p) : c(c), p(p), next(NULL) {}

    C getDataC() {
      return this->c;
    }

    P getDataP() {
      return this->p;
    }

    void setData(C c, P p) {
      this->c = c; this->p = p;
    }
  private:
    C c; P p;
};

// 排序双值链表
template <class C, typename P> class PairedSortedList {
  public:
    PairedSortedList() {
      size = 0;
    }

    void insert(C c, P p) {
      PairedListNode<C, P> *m = new PairedListNode<C, P>(c, p);

      if (size == 0) {
        // cout << "Inserted to head: " << c << " " << p << endl;
        head = m; size = 1; return;
      }

      // 比头节点小，插到头之前
      if (p < head->getDataP()) {
        m->next = head;
        head = m;
        size++;
        // cout << "Inserted before head: " << c << " " << p << endl;
        return;
      }

      // 找到比下一个节点小的地方，插进去
      PairedListNode<C, P> *t = head;
      while (t->next) {
        if (p <= t->next->getDataP()) break;
        // cout << t->next->getDataP() << " < " << p << endl;
        t = t->next;
      }
      PairedListNode<C, P> *o = t->next;
      t->next = m;
      m->next = o;
      size++;
    }

    PairedListNode<C, P>* remove() {
      if (size == 0) return NULL;
      PairedListNode<C, P>* t = head;
      head = head->next;
      size--;
      return t;
    }

    void removeNode(PairedListNode<C, P>* node) {
        if (size == 0) return;
        if (node == head) {
            remove(); return;
        }
        PairedListNode<C, P>* t = head;
        for (int i = 0; i < size - 1; i++) {
            if (t->next == node) {
                // 删掉这个节点
                t->next = node->next;
                node->next = NULL;
                size--;
                return;
            }
        }
    }

    PairedListNode<C, P>* removeLast() {
      if (size == 0) return NULL;
      if (size == 1) {
        size--;
        PairedListNode<C, P>* t = head;
        head = NULL;
        return t;
      }
      PairedListNode<C, P>* t = head;
      for (int i = 0; i < size - 2; i++)
        t = t->next;
      PairedListNode<C, P>* tail = t->next;
      t->next = NULL;
      size--;
      return tail;
    }

    int getSize() {
        return size;
    }
  private:
    PairedListNode<C, P> *head;
    int size;
};

template <typename T> class BinaryTreeNode {
  public:
    BinaryTreeNode() :
      BinaryTreeNode(NULL, NULL, NULL, NULL) {}

    BinaryTreeNode(T data) :
      BinaryTreeNode(data, NULL, NULL, NULL) {}

    BinaryTreeNode(T data, BinaryTreeNode *lchild, BinaryTreeNode *rchild) :
      BinaryTreeNode(data, lchild, rchild, NULL) {}

    BinaryTreeNode(T data, BinaryTreeNode *lchild, BinaryTreeNode *rchild, BinaryTreeNode *parent) :
      data(data), lchild(lchild), rchild(rchild), parent(parent) {

        if (lchild)
          lchild->parent = this;
        if (rchild)
          rchild->parent = this;

      }

    void setLchild(BinaryTreeNode *lchild) {
      this->lchild = lchild;
    }

    void setRchild(BinaryTreeNode *rchild) {
      this->rchild = rchild;
    }

    void setParent(BinaryTreeNode *parent) {
      this->parent = parent;
    }

    T getData() {
      return this->data;
    }

    void setData(T data) {
      this->data = data;
    }

    BinaryTreeNode *getLchild() {
      return this->lchild;
    }

    BinaryTreeNode *getRchild() {
      return this->rchild;
    }

    BinaryTreeNode *getParent() {
      return this->parent;
    }

    void createLchild(T data) {
      BinaryTreeNode<T> *t = new BinaryTreeNode<T>(data);
      this->lchild = t;
      t->parent = this;
    }

    void createRchild(T data) {
      BinaryTreeNode<T> *t = new BinaryTreeNode<T>(data);
      this->rchild = t;
      t->parent = this;
    }

    void createLParent(T data) {
      BinaryTreeNode<T> *t = new BinaryTreeNode<T>(data);
      t->setRchild(this);
      this->parent = t;
    }

    void createRParent(T data) {
      BinaryTreeNode<T> *t = new BinaryTreeNode<T>(data);
      t->setLchild(this);
      this->parent = t;
    }

  private:
    T data;
    BinaryTreeNode *lchild, *rchild, *parent;
};

// 0->DLR 1->LDR 2->LRD
#define DLR 0
#define LDR 1
#define LRD 2

template <typename T> class BinaryTree {
  public:
    BinaryTree() : BinaryTree(*(new T)) {}

    BinaryTree(T data) : BinaryTree(data, 64) {}

    BinaryTree(T data, int size) {
      root = new BinaryTreeNode<T>(data);
      nodeCount = 1;
      this->size = size;
    }

    BinaryTreeNode<T> *walkTree(int method, BinaryTreeNode<T> *node, T data,
        // 类中的函数指针前要加类名，否则unresolved overloaded function type
        bool (BinaryTree::*judgeFunc)(BinaryTreeNode<T>*, T) ) {
      // method: 遍历方式
      // 0->DLR 1->LDR 2->LRD
      BinaryTreeNode<T> *t;
      if (method == 0) goto walkMe;

      walkLeft: // 遍历左节点
      if (node->getLchild() != NULL) {
        t = walkTree(method, node->getLchild(), data, judgeFunc);
        if (t != NULL) return t;
      }
      if (method == 1) goto walkMe;

      walkRight: // 遍历右节点
      if (node->getRchild() != NULL) {
        t = walkTree(method, node->getRchild(), data, judgeFunc);
        if (t != NULL) return t;
      }
      if (method == 0 || method == 1) goto walkEnd;


      walkMe: // 看自己
      if (judgeFunc != NULL) {
        if ((this->*judgeFunc)(node, data)) {
          return node;
        }
      }
      if (method == 0) goto walkLeft;
      else if (method == 1) goto walkRight;

      walkEnd: // 啥都找不到
      return NULL;
    }

    void createLeftParent(BinaryTreeNode<T> *node, T data) {
      BinaryTreeNode<T> *t = new BinaryTreeNode<T>(data);
      t->setRchild(node);
      node->setParent(t);
      nodeCount++;
    }

    void createRightParent(BinaryTreeNode<T> *node, T data) {
      BinaryTreeNode<T> *t = new BinaryTreeNode<T>(data);
      t->setLchild(node);
      node->setParent(t);
      nodeCount++;
    }

    void createLchild(BinaryTreeNode<T> *node, T data) {
      BinaryTreeNode<T> *t = new BinaryTreeNode<T>(data);
      t->setParent(node);
      node->setLchild(t);
      nodeCount++;
    }

    void createRchild(BinaryTreeNode<T> *node, T data) {
      BinaryTreeNode<T> *t = new BinaryTreeNode<T>(data);
      t->setParent(node);
      node->setRchild(t);
      nodeCount++;
    }

    void fillData(BinaryTreeNode<T> *node, T l, T r, T m) {
      node->setData(m);
      if (l != -1)
        createLchild(node, l);
      if (r != -1)
        createRchild(node, r);
    }

    void findNodeFillData(T m, T l, T r) {
      BinaryTreeNode<T> *t = walkTree(LRD, root, m, this->isEqual);
      fillData(t, l, r, m);
    }

    void showAllNodes() {
      walkTree(LRD, root, 0, this->displayNode);
    }

    void findSumPath(int sum) {
      walkTree(DLR, root, sum, this->findSumPath);
    }

    int getNodeCount() {
      return nodeCount;
    }

  protected:
    int nodeCount, size;
    BinaryTreeNode<T> *root;
    bool isEqual(BinaryTreeNode<T> *node, T data) {
      if (node->getData() == data) return true;
      return false;
    }

    bool displayNode(BinaryTreeNode<T> *node, T data) {
      cout << node->getData() << endl;
      return false;
    }

};

#define HUFFMAN_PREFIX_COUNT 8
class HuffmanTree : public BinaryTree<char> {
  public:
    HuffmanTree(float p[HUFFMAN_PREFIX_COUNT]) : BinaryTree() {
      // 构造二叉树集合
      PairedSortedList<BinaryTreeNode<char>*, float> l;
      for (int i = 0; i < HUFFMAN_PREFIX_COUNT; i++) {
        l.insert(new BinaryTreeNode<char>('A' + i), p[i]);
      }
      // 集合中只剩下一棵树即停止
      while (l.getSize() > 1) {
        PairedListNode<BinaryTreeNode<char>*, float> *t1, *t2;
        // l是排序链表，t1对应的p小于t2的
        t1 = l.remove(); t2 = l.remove();
        // t1放左节点，这个新的根节点的权重设为两子节点的相加
        BinaryTreeNode<char> *t = new BinaryTreeNode<char>(0, t1->getDataC(), t2->getDataC());
        l.insert(t, t1->getDataP() + t2->getDataP());
      }
      // 集合中唯一的树就是该死的赫夫曼树
      root = l.remove()->getDataC();
    }

    stringstream getHuffmanPath(BinaryTreeNode<char>* node) {
      stringstream t; Stack<int> s(HUFFMAN_PREFIX_COUNT);
      while (node->getParent()) {
        if (node->getParent()->getLchild() == node) {
          s.push(0);
        } else if (node->getParent()->getRchild() == node){
          s.push(1);
        }
        node = node->getParent();
      }
      int len = s.getStackLength();
      for (int i = 0; i < len; i++) {
        t << s.pop();
      }
      return t;
    }

    stringstream showHuffmanTreeCodec() {
      stringstream ss;
      for (int i = 0; i < HUFFMAN_PREFIX_COUNT; i++) {
        char cur = 'A' + i;
        BinaryTreeNode<char>* ht = walkTree(DLR, this->root, cur, this->isEqual);
        //cout << cur << ":";
        ss << cur << ":";
        stringstream t = getHuffmanPath(ht);
        //cout << t.str() << endl;
        ss << t.str() << endl;
        huffmanPathLen[i] = t.str().length();
      }
      return ss;
    }

    char walkHuffmanTree(BinaryTreeNode<char>* node, string hc, int i) {
      if (node->getData()) {
        return node->getData();
      }
      if (hc[i] != '0' && hc[i] != '1' || i >= hc.length()) {
        //cout << "hc[" << i << "] = " << (int) hc[i] << ", len = " << hc.length() << endl;
        throw 1;
      }
      return walkHuffmanTree((hc[i] == '0') ? node->getLchild() : node->getRchild(), hc, i + 1);
    }

    string decodeHuffmanCodec(string hc) {
      string t = "";
      for (int i = 0; i < hc.length(); ) {
        char c = walkHuffmanTree(this->root, hc, i);
        i += huffmanPathLen[c - 'A'];
        t += c;
      }
      return t;
    }
  private:
    int huffmanPathLen[HUFFMAN_PREFIX_COUNT];
};

int main() {
  cout << "Hello" << endl;
  float p[HUFFMAN_PREFIX_COUNT];
  ifstream in("input1.txt");
  ofstream o1("output1.txt");
  float sum = 0; int caught = 0;
  try {
    // = {0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11};
    for (int i = 0; i < HUFFMAN_PREFIX_COUNT; i++) {
      if (i != 0) {
        char comma; in >> comma;
        if (comma != ',') {
          throw 11;
        }
      }
      in >> p[i];
      if (in.fail() || p[i] >= 1 || p[i] <= 0) {
        throw 12;
      }
      sum += p[i];
    }
    if (sum != 1) throw 13;

  } catch (int ex) {
    o1 << "ERROR" << endl;
    o1.close();
    return -1;
  }

  HuffmanTree hft(p);
  string codec = hft.showHuffmanTreeCodec().str();
  cout << codec << endl;
  o1 << codec << endl;
  o1.close();

  ifstream in2("input2.txt");
  ofstream o2("output2.txt");
  string line = "";
  while (true) {
    in2 >> line;
    if (line == "" || in2.fail()) break;
    try {
      cout << hft.decodeHuffmanCodec(line) << endl;
      o2 << hft.decodeHuffmanCodec(line) << endl;
    } catch (int ex) {
      cout << "ERROR" << endl;
      o2 << "ERROR" << endl;
    }
  }
  o2.close();

}
